{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Candies Allocated to K Children"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumCandies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个小孩最多能分到多少糖果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>下标从 0 开始</strong> 的整数数组 <code>candies</code> 。数组中的每个元素表示大小为 <code>candies[i]</code> 的一堆糖果。你可以将每堆糖果分成任意数量的 <strong>子堆</strong> ，但 <strong>无法</strong> 再将两堆合并到一起。</p>\n",
    "\n",
    "<p>另给你一个整数 <code>k</code> 。你需要将这些糖果分配给 <code>k</code> 个小孩，使每个小孩分到 <strong>相同</strong> 数量的糖果。每个小孩可以拿走 <strong>至多一堆</strong> 糖果，有些糖果可能会不被分配。</p>\n",
    "\n",
    "<p>返回每个小孩可以拿走的 <strong>最大糖果数目</strong><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candies = [5,8,6], k = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candies = [2,5], k = 11\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= candies.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= candies[i] &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>12</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-candies-allocated-to-k-children](https://leetcode.cn/problems/maximum-candies-allocated-to-k-children/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-candies-allocated-to-k-children](https://leetcode.cn/problems/maximum-candies-allocated-to-k-children/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,8,6]\\n3', '[2,5]\\n11']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        sumOfcandies = sum(candies)\n",
    "        def f1(target):\n",
    "            cnt = 0\n",
    "            for i in candies:\n",
    "                cnt += i // target\n",
    "            return cnt >= k\n",
    "            \n",
    "            \n",
    "        i = 1\n",
    "        j = max(candies) + 1\n",
    "        while i < j:\n",
    "            mid = (i + j) >> 1\n",
    "            if f1(mid):\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid\n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        max_c = max(candies)\n",
    "        sum_c = sum(candies)\n",
    "        if sum_c < k:\n",
    "            return 0\n",
    "        if sum_c == k:\n",
    "            return 1\n",
    "        \n",
    "        def check(mid):\n",
    "            res = 0\n",
    "            for c in candies:\n",
    "                res += c // mid\n",
    "            return res >= k\n",
    "\n",
    "        left, right = 1, max_c\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return left - 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def check(v):\n",
    "            count = 0\n",
    "            for c in candies:\n",
    "                count += c//v\n",
    "            if count >= k:\n",
    "                return True\n",
    "            return False\n",
    "        msum = sum(candies)\n",
    "        i = 1\n",
    "        j = msum//k\n",
    "        rst = 0\n",
    "        while i <= j:\n",
    "            mid = (i+j)//2\n",
    "            status = check(mid)\n",
    "            if status:\n",
    "                rst = max(rst, mid)\n",
    "                i = mid+1\n",
    "            else:\n",
    "                j = mid-1\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\r\n",
    "        left, right = 0, max(candies)\r\n",
    "        res = 0\r\n",
    "        while left <= right:\r\n",
    "            mid = left + (right - left) // 2\r\n",
    "            if mid == 0:\r\n",
    "                left = mid + 1\r\n",
    "                continue\r\n",
    "            num = 0\r\n",
    "            for candy in candies:\r\n",
    "                num += candy // mid\r\n",
    "            if num >= k:\r\n",
    "                res = max(res, mid)\r\n",
    "                left = mid + 1\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def check(cnt: int) -> bool:\n",
    "            # 每个孩子分 cnt 个糖果，判断 k 个孩子是否够分\n",
    "            return sum(candy // cnt for candy in candies) >= k\n",
    "\n",
    "        lo, hi = 1, max(candies) + 1\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "            \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        if sum(candies) < k: return 0\n",
    "        l, r = 0, int(1e8)\n",
    "\n",
    "        def judge(num):\n",
    "            return sum([x // num for x in candies]) >= k\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if judge(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        # problems to solve:\n",
    "        # get max number of candies\n",
    "        # set l,r as 1 and max candies, for each kid, how many candi can separate into number of candies in between [l,r]\n",
    "        # as numbers in [l,r] is as divider, so, we let l,r +1 separately, and return l-1 at last\n",
    "        def count(candy):\n",
    "            ret = sum([cur // candy for cur in candies])\n",
    "            return ret >= k\n",
    "        l,r = 1,max(candies)+1\n",
    "        while l < r:\n",
    "            mid = l + ((r-l) >> 1)\n",
    "            if count(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def check(candies, n, k):\n",
    "            return sum([candy // n for candy in candies]) >= k if n else True\n",
    "        total = sum(candies)\n",
    "        left, right = 1, total // k\n",
    "        if total < k:\n",
    "            return 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(candies, mid, k):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def get_max_candy(num: int) -> int:\n",
    "            return sum([candy // num for candy in candies])\n",
    "\n",
    "        sum_candy = sum(candies)\n",
    "        if sum_candy < k:\n",
    "            return 0\n",
    "        l, r = 1, sum_candy // k + 1\n",
    "        while l < r:\n",
    "            m = l + ((r - l) >> 1)\n",
    "            if get_max_candy(m) >= k:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def check(mx):\n",
    "            f = [0]*len(candies)\n",
    "            for i, num in enumerate(candies):\n",
    "                f[i] = num//mx\n",
    "            return sum(f)>=k\n",
    "\n",
    "        if sum(candies) < k:\n",
    "            return 0\n",
    "        left = 1\n",
    "        right = max(candies) + 1\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        # 判断每个小孩分到 i 个糖果时是否可以满足要求\n",
    "        def check(i: int) -> bool:\n",
    "            res = 0\n",
    "            for c in candies:\n",
    "                res += c // i\n",
    "            return res >= k\n",
    "\n",
    "        # 二分查找\n",
    "        l = 1\n",
    "        r = max(candies)\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        if sum(candies) < k:\n",
    "            return 0\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for y in candies:\n",
    "                cnt += y // x\n",
    "            return cnt >= k\n",
    "        \n",
    "        l, r = 1, max(candies)\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        # 由于 x 越大 sum 越小，而 key 需要一个增函数（非减），因此对 sum 取相反数从而满足要求\n",
    "        return bisect_right(range(sum(candies) // k), -k, key=lambda x: -sum(v // (x + 1) for v in candies))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        return bisect_right(range(sum(candies) // k), -k, key=lambda x: -sum(v // (x + 1) for v in candies))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def check(v: int):\n",
    "            if v == 0: return True\n",
    "            return (sum(x // v for x in candies) >= k)\n",
    "\n",
    "        l = 0\n",
    "        r = sum(candies) // k\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            if x == 0:\n",
    "                return True\n",
    "            y = 0\n",
    "            for candy in candies:\n",
    "                y += candy//x\n",
    "            return y>=k\n",
    "        l,r = 0,sum(candies)//k+1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            print(l,r)\n",
    "            if check(mid):\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        # if check(l):\n",
    "        return l-1\n",
    "        # else:\n",
    "        #     return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCandies(self, candies: List[int], k: int) -> int:\n",
    "        if sum(candies) < k:\n",
    "            return 0\n",
    "        left, right = 0, max(candies)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if sum([x // mid for x in candies]) >= k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
